The invention is generally relates to computers and computer software. More specifically, the invention relates to the management of data structures and functions in an object oriented programming system.
Managing available memory is critically important to the performance and reliability of a computer system. Such systems must store vast quantities of data within limited memory address space. Such data is commonly stored in the form of xe2x80x9cobjects.xe2x80x9d Memory space allocated for an object is known as an object heap. Typically each computer program has its own object heap.
Objects comprise both data structures and operations, known collectively as methods. Methods access and manipulate data structures. Objects having identical data structures and common behavior can be grouped together into classes. Each object inherits the data structure and methods of the particular class from which it was instantiated. Further, a hierarchical inheritance relationship exists between multiple classes. For example, one class may be considered a parent of another, child class. The child class is said to be derived from the parent class and thus, inherits all of the attributes and methods of the parent class.
Object structure includes data and pointer fields. Pointers contain the addresses of other memory locations; data fields embody information or other objects. The object 10 of FIG. 1 has an identifier field 12, data field 14 and pointers 16, 18. The identifier field 12 contains processing instructions used only when the object 10 is compiled, so it is not necessarily stored with the object 10. A dashes distinguish the identifier field 12 from information stored at run time.
In the figure, pointers 16 are represented as arrows pointing to other objects 20. A nil value of pointer 18 is represented by an xe2x80x9cXxe2x80x9d within the corresponding pointer field. Items 14 are contained by the object and are referred to as internal objects, while objects 20 referenced by the object""s 10 pointers are known as external objects.
The exemplary object 10 also has names 22 associated with it. Each name is a labeled pointer to the object. Since names are only used by the compiler at compile time, they do not require any storage at run time. This fact is represented by the use of dashed boxes to enclose the name pointers. Note that external objects can also contain pointers to other objects recursively, creating an object with arbitrary xe2x80x9cdepth.xe2x80x9d
The depth of an object is determined by counting the number of pointers that must be followed to reach it, starting from a name. Thus in the figure, names 22 are at depth 0, the object 10 is at depth 1, and the external objects 20 are at depth 2. For consistency, the depth attributed to the manipulation of a pointer corresponds to the depth at which the pointer is stored. Thus, manipulations of pointers 16 as shown in FIG. 1 are considered to be at depth 1.
Whenever a program creates a new object, available memory is reserved using a process known as memory allocation. The Java programming environment developed by Sun Microsystems is one example of a programming framework that utilizes memory allocation. Given the limited amount of memory available in such an environment, it is important to deallocate memory reserved for data no longer in use. Otherwise, system performance will suffer as available memory is consumed.
A computer program known as a garbage collector empties unused memory that has been allocated by other programs. Generally, a garbage collection algorithm carries out storage management by automatically reclaiming storage. Garbage collectors are typically activated when an object heap becomes full. A key functionality of a garbage collection algorithm involves determining if an object is no longer reachable by an executing program. A properly collectable object must be unreachable either directly or through a chain of pointers.
Thus, the garbage collector must identify pointers directly accessible to the executing program. Further, the collector must identify references contained within that object, allowing the garbage collector to transitively trace chains of pointers. When the data structure of an object is deemed unreachable, the garbage collector reclaims memory. The memory is deallocated even if it has not been explicitly designated by the program.
Specific methods for memory reclamation include reference counting, mark-scan and the copying garbage collection. In reference counting collection, as diagramed in FIG. 2, each external object 20 is associated with a count 24 reflecting the number of objects that point to it. Every time a new pointer implicates an external object 20, the count 24 is incremented. Conversely, the count 24 is decremented every time an existing reference is destroyed. When the count 24 goes to zero, the object 20 and its associated count 24 are deallocated.
A variation of the reference counting scheme known as weighted reference counting removes the requirement of referencing shared memory, but some bookkeeping is still required at run time. Another variation known as lazy reference counting reduces the run-time CPU requirements by deferring deallocation operations and then combining them with allocations, but does not eliminate them entirely.
An alternative method, called mark-scan garbage collection, never explicitly deallocates external objects. Periodically, the garbage collection process marks all data blocks that can be accessed by any object. Unreachable memory is reclaimed by scanning the entire memory and deallocating unmarked elements.
Each cycle of the mark-scan algorithm sequentially operates in mark and sweep stages. In the mark stage, the collector scans through an object heap beginning at its roots, and attempts to mark objects that are still reachable from a root. An object is deemed reachable if it is referenced directly by a root or by a chain of objects reachable from a root. In the sweep stage, the collector scans through the objects and deallocates any memory reserved for objects that are unmarked as of completion of the mark stage. Some variations of mark-scan require that active program threads be halted during collection, while others operate concurrently.
Copying garbage collectors are similar to those of the mark-scan variety. However, instead of marking those items that can be reached by reference, all reachable data structures are periodically copied from one memory space into another. The first memory space can then be reclaimed in its entirety. A specific implementation of a copying garbage collector is a generational garbage collector, which partitions an object heap into new and old partitions. A generational garbage collector relies on a tendency for newer objects to cease to be used more frequently than older objects. Put another way, as an object is used over time, it becomes less and less likely that the object will cease being used.
A generational garbage collector manages an object heap by scanning through newer objects in a new partition of the heap. The collector deallocates memory for objects that are no longer in use, and move objects that live beyond a predetermined period into an old partition. Given that older objects tend to be more stable, typically no scanning of the old partition of the object heap is required.
Despite the progresses afforded by the above garbage collection techniques, obstacles to memory management remain. One particular area of concern relates to xe2x80x9cshort livedxe2x80x9d objects. Although such objects may be used only briefly, they tend to linger and take up space in the object heap between garbage collection cycles. Further, the overhead associated with allocating and deallocating short lived objects is disproportionally high relative to xe2x80x9clonger livedxe2x80x9d objects.
Deallocating processes require the computer to perform certain operations that are outside of normal productive operations. These additional processes burden the overall operation of the computer. Therefore, for both performance and storage concerns, it is desirable to minimize the occurrence of short lived objects. For instance, a programmer conducting a debugging operation could consolidate the functionality of a located short lived object into a long lived one. However, this task is complicated by the absence of an accurate method of calculating the life span of an object. Currently, a programmer is relegated to estimating life spans as a function of the time that the object is collected. Since the initiation of a garbage collection cycle does not necessarily coincide with when an object becomes unreachable, conventional life span measurements include periods where the object is actually defunct. Therefore a significant need exists for a manner of accurately calculating the lifetime of an object.
The present invention involves a method, computer system and program product operable to calculate a life span of an object. The invention determines when an object is created and when it becomes collectable. A processor conducts a garbage collection trace algorithm on a method boundary to determine when the object becomes unreachable. In one embodiment, the frequency with which the trace algorithm is performed is modified via a user interface. In another application consistent with the invention, the processor conducts the trace algorithm at every method exit.
Trace data pertaining to the algorithm is stored along with other data relating to method entry and exit, as well as to object creation. A visualizer program displays the trace data to the user. In one embodiment, the user locates an object within an object oriented programing environment based on the life span of the object. Another embodiment allows the user to determine what method was running at the time that the object became collectable.
The above and other objects and advantages of the present invention shall be made apparent from the accompanying drawings and the description thereof.